1. Field of the Invention
The present invention relates to a method and an apparatus for determining wiring routes by utilizing an artificial neural network in which wiring problems in large-scale integrated circuits are solved.
2. Description of the Background Art
As usual, in the case where wiring routes are determined in large-scale integrated (LSI) circuits, on condition that locations of the circuit compositions are provided on the chip in which the circuit is arranged and a group of wires are regarded as a group of two-terminal nets (wires for connecting between the circuit compositions), there are so-called wiring problems for determining the wiring routes while satisfying the electrical and physical conditions.
The above wiring problems are treated as the problems for determining the routes of all two-terminal nets (wiring nets). In this case, it is assumed that wiring capacity exists in the boundary dividing the areas which are normally provided in a two-dimensional wiring grid, where the wiring capacity refers to the allowable number of wires passing through the boundary between the areas.
In a conventional method for solving the above wiring problems, for example, a maze method is known (see, C.Y. IRE Trans. on Electronic Computers, pp. 346-365 Sep. 1961). In the method, an algorithm in which a wiring designer determines the wiring routes in the grid by attaching an label to each area in turn from a starting point while avoiding wiring forbidden areas is repeated until arriving at a goal point or being impossible to attach the label because a new area to be attached to the label is not able to be found.
According to the above method, the designer can always reach the goal point for a single wire if a wiring route to be determined exists. Moreover, the determined route is the shortest one.
However, because the maze method is the algorithm for determining all wiring routes in turn, a lot of time is consumed to determine all wiring routes in a LSI circuit with a large number of wires. Moreover, it is required to set the order of the wiring in advance so that the determination of the wiring routes is sometimes impossible if the order of the wiring is not adequate even if through wiring routes exist.
Further, the determination of the wiring order depends on the arrangement of the circuit and the circuit compositions so that it is difficult to make a general guide.
Therefore, when it is impossible to determine a wiring route in the conventional wiring method, the wiring route is normally corrected by hand or an automatic tearing-off-rewiring method is utilized. In the automatic tearing-off-rewiring method, a wiring route determined by attaching the label is cancelled by tearing the label off and a new wiring route is determined.
Therefore, in the case where the wiring route is corrected by hand, it takes much time and it is difficult to determine the wiring routes so that wiring errors easily occur. On the other hand, in the case where the automatic tearing-off-rewiring method is utilized, because a turning-back work called as a back track is performed, a working time increases.
As mentioned above, in the case where the wiring problems of LSI circuit are solved by utilizing the conventional method, the wiring routes are determined in turn while consuming the much time. Moreover, it is sometimes impossible to determine the wiring routes when the wiring order is not adequate.